iT邦幫忙

2024 iThome 鐵人賽

DAY 15
0

題目

1371. Find the Longest Substring Containing Vowels in Even Counts

題意

給定一字串s,求最長子字串長度,使得子字串中的每種母音數量都是偶數個。

方向

用一個真假值陣列儲存索引零到當前元素的母音數量狀態,我是是直接存各母音是否為偶數
若0~i的母音狀態與0~j的母音狀態相同,則i~j的各母音數數量必為偶數,因為每種母音都要改變兩次狀態才能變回原樣,而兩次即是偶數。

因此這題的關鍵就是狀態的資料結構選擇,以及查找第一次出現相同狀態的索引值。我這裡是用布林陣列,再用布林陣列做為鍵值做哈希表。

實作

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int n = (int)s.length();
        vector<bool> is_even(5, true); // a e i o u
        
 // is_even -> first appear index 
        unordered_map<vector<bool>, int> um;
        // Number of vowels are even at first
        um[is_even] = -1;
        
        int res = 0;
        for(int i = 0; i < n; i++)
            {
            char c = s[i];
            if(c == 'a')
                is_even[0] = !is_even[0];
            if(c == 'e')

                is_even[1] = !is_even[1];
            if(c == 'i')

                is_even[2] = !is_even[2];
            if(c == 'o')

                is_even[3] = !is_even[3];
            if(c == 'u')

                is_even[4] = !is_even[4];
            if(um.find(is_even) != um.end())
                res = max(res, i - um[is_even]);
            else
                um[is_even] = i;
        }
        return res;
        
    }
};         

分析

若字串長度為N
時間複雜度:O(N)
空間複雜度:O(N)

結果

Time Submitted Status Runtime Memory Language
09/15/2024 10:05 Accepted 209 ms 20.1 MB cpp

上一篇
[9/14] 連續最大值的長度
下一篇
[9/16] 最短時間差
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言